package com.itzmn.datastructure.newcode;

/**
 * @Author: 张梦楠
 * @Date: 2018/12/30 19:19
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 更新版的堆排序
 *
 *  首先将数组建堆，
 *  建堆，
 *  修改堆，
 *  将堆头与最后一位交换，然后调整剩下的堆
 *
 */
public class HeapSort_1 {

    public static void main(String[] args) {

        new HeapSort_1().init();
    }

    private void init() {
        int[] arr = {2,6,7,3,1,5,9};
        for (int i=0; i<arr.length; i++){
            heapInsert(arr,i);
        }
        for (int i=0; i<arr.length;i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        // 以上构成了一个大根堆
        // 将堆顶与最后一个元素交换
        int heapSize = arr.length;
        swap(arr,0,--heapSize);

        // 重新建立堆，在新的数组
        while (heapSize > 0){
            heapify(arr,0,heapSize);
            swap(arr,0,--heapSize);
        }
        for (int i=0; i<arr.length;i++){
            System.out.print(arr[i] + " ");
        }

    }

    /**
     * 构建一个大根堆
     * @param arr
     * @param index 插入的数据的位置
     */
    private void heapInsert(int[] arr,int index){
            while (arr[index] > arr[(index-1)/2]){
                // 如果当前位置的数据，比父亲大，那么交换数据
                swap(arr,index,(index-1)/2);
                // 将父亲设置为当前位置
                index = (index-1)/2;
            }
    }


    /**
     * 调整堆，变为大根堆
     * @param arr
     * @param start 堆的起始位置,从这个位置开始调整
     * @param heapSize 堆的节点数
     */
    private void heapify(int[] arr,int start,int heapSize){

        // 节点的左子节点
        int left = start*2+1;
        // 左子节点不能越界，也就是数据向下移动的时候，不能出数组
        while (left < heapSize) {
            // 得到左右子节点最大的那个
            int largest = left + 1 < heapSize && arr[left] < arr[left + 1]
                    ? left + 1 : left;

            largest = arr[largest] > arr[start] ? largest : start;

            if (largest == start) {
                break;
            }

            swap(arr,start,largest);
            start = largest;
            left = start *2 +1;
        }
    }

    /**
     * 交换数组中两个位置
     * @param arr
     * @param index
     * @param i
     */
    private void swap(int[] arr, int index, int i) {
        int temp = arr[index];
        arr[index] = arr[i];
        arr[i] = temp;
    }


}
